/*
Source : https://leetcode.com/problems/3sum/
Author : nflush@outlook.com
Date   : 2016-06-27
*/
/*
15. 3Sum
Total Accepted: 125393 Total Submissions: 652451 Difficulty: Medium

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Subscribe to see which companies asked this question
*/

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int i=0,j=0,k;
        int max = nums.size();
        std:sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        vector<int> asn;
        for (i=0;i<max-2;i++){
            if(i!=0&&nums[i]==nums[i-1]) continue;
            for (j=i+1, k=max-1;j<k;){
                if(j!=i+1&&nums[j]==nums[j-1]){
                    j++;
                    continue;
                }
                int sum = nums[i]+nums[j]+nums[k];
                if (sum == 0){
                    asn.clear();
                    asn.push_back(nums[i]);
                    asn.push_back(nums[j]);
                    asn.push_back(nums[k]);
                    ret.push_back(asn);
                    j++;
                } else if(sum > 0){
                    k--;
                } else {
                    j++;
                }
            }
        }
        return ret;
    }
};
